// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。

// 思路： 单调递增栈，当遇到小于栈顶的元素时，出栈并计算面积，并更新最大面积
// 时间复杂度：O(n)，n是heights的长度
// 空间复杂度：O(n)，stack的大小

function largestRectangleArea(heights) {
    let stack = [0]
    let res = 0
    // 确保所有柱子都能被处理
    heights.unshift(0)
    heights.push(0)
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
            let curIdx = stack.pop()
            let h = heights[curIdx]
            // i是右边界，stack[stack.length - 1]是左边界，计算区间距离，不包括左右边界
            let w = i - stack[stack.length - 1] - 1
            res = Math.max(res, w * h)
        }  
        stack.push(i)      
    }
    return res
}


let heights = [2,1,5,6,2,3]
console.log(largestRectangleArea(heights))